#include <iostream>
#include <assert.h>
#include <vector>
#include <string>

using namespace std;

#include "RBTree.h"
#include "AVLTree.h"

void test1()
{
	int arr[] = { 45,1,7,67,34,76,2,9,0,6,16 };
	RBTree<int, int> r1;

	for (auto e : arr)
	{
		r1.insert(make_pair(e, e));
		r1.InOrder();
		cout << endl;
	}
	cout << r1.GetRotateNum() << endl;
}

void test2()
{
	const int N = 1000;
	srand(time(0));

	RBTree<int, int> r;
	for (int i = 0; i < N; i++)
	{
		int randnum = rand();
		r.insert(make_pair(randnum, randnum));
		cout << randnum << ' ' << r.IsRBTree() << endl;
	}

	r.InOrder();

	cout << r.IsRBTree() << endl;
	cout << "旋转次数: " << r.GetRotateNum() << endl;
}

void test3()
{
	const int N = 10000000;
	srand(time(0));

	vector<int> v;
	v.reserve(N);

	int n = 0;
	for (int i = 0; i < N; i++)
	{
		v.push_back(rand() + n);
		n++;
	}

	RBTree<int, int> rbt;
	AVLTree<int, int> avlt;

	for (auto e : v)
	{
		rbt.insert(make_pair(e, e));
		avlt.Insert(make_pair(e, e));
	}

	cout << "红黑树的旋转次数：" << rbt.GetRotateNum() << endl;
	cout << "红黑树的高度：" << rbt.Height() << endl;
	cout << endl;
	cout << "AVL树的旋转次数：" << avlt.GetRotateNum() << endl;
	cout << "AVL树的高度：" << avlt.Height() << endl;
}

int main()
{
	//test1();

	//test2();

	test3();

	return 0;
}
